package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description: 554. 砖墙
 * <p>
 * 你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。
 * <p>
 * 你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
 * <p>
 * 给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
 * 输出：2
 * <p>
 * 示例 2：
 * <p>
 * 输入：wall = [[1],[1],[1]]
 * 输出：3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/brick-wall
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2023/3/15 10:21
 */
public class Solution_554 {

    private static Solution_554 instance = new Solution_554();

    public static void main(String[] args) {
        List<List<Integer>> wall = new ArrayList<>();
        wall.add(new ArrayList<Integer>() {{
            add(1);
            add(2);
            add(2);
            add(1);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(3);
            add(1);
            add(2);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(1);
            add(3);
            add(2);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(2);
            add(4);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(3);
            add(1);
            add(2);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(1);
            add(3);
            add(1);
            add(1);
        }});
        // ===================
       /* wall.clear();
        wall.add(new ArrayList<Integer>() {{
            add(1);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(1);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(1);
        }});
        // ===================
        wall.clear();
        wall.add(new ArrayList<Integer>() {{
            add(1);
            add(1);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(2);
        }});
        wall.add(new ArrayList<Integer>() {{
            add(1);
            add(1);
        }});*/
        System.out.println(instance.leastBricks(wall));
        System.out.println(instance.leastBricks_v2(wall));
    }

    /**
     * 参考Solution_554_2.png
     * <p>
     * 第 1 行的间隙有 [1,3,5]
     * 第 2 行的间隙有 [3,4]
     * 第 3 行的间隙有 [1,4]
     * 第 4 行的间隙有 [2]
     * 第 5 行的间隙有 [3,4]
     * 第 6 行的间隙有 [1,4,5]
     * 对间隙计数完成后，遍历「哈希表」找出出现次数最多间隙 4，根据同一个间隙编号只会在单行内被统计一次，用总行数减去出现次数，即得到「最少穿过的砖块数」。
     * <p>
     * 作者：AC_OIer
     * 链接：https://leetcode.cn/problems/brick-wall/solution/gong-shui-san-xie-zheng-nan-ze-fan-shi-y-gsri/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param wall
     * @return
     */
    public int leastBricks_v2(List<List<Integer>> wall) {
        /**
         * key: index
         * val: times
         */
        int wide = 0;
        Map<Integer, Integer> numTimeMap = new HashMap<>();
        int N = wall.size();
        for (int i = 0; i < N; i++) {
            int index = 0;
            for (int j = 0; j < wall.get(i).size(); j++) {
                index += wall.get(i).get(j);
                numTimeMap.put(index, numTimeMap.getOrDefault(index, 0) + 1);
            }
            wide = index;
        }
        int maxTimes = 0;
        for (Map.Entry<Integer, Integer> m : numTimeMap.entrySet()) {
            if (maxTimes < m.getValue() && m.getKey() != wide) {// 排除m.getKey() != wide，可以通过用例体会！！！
                maxTimes = m.getValue();
            }
        }
        return N - maxTimes;
    }

    /**
     * 内存不够
     *
     * <p>
     * [[100000000],[100000000],[100000000]]
     * <p>
     * 不需要创建100000000列
     *
     * @param wall
     * @return
     */
    public int leastBricks(List<List<Integer>> wall) {
        int N = wall.size();
        List<Integer> list = wall.get(0);
        int M = 2;
        for (Integer num : list) {
            M += num;
        }
        /**
         * 坐标交叉点
         * true：通
         * false：不通
         */
        boolean dp[][] = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            int index = 0;
            for (int j = 0; j < wall.get(i).size() - 1; j++) {
                index += wall.get(i).get(j);
                dp[i][index] = true;
            }
        }
        int ans = N;
        for (int j = 1; j < M - 1; j++) {
            int tmp = 0;
            for (int i = 0; i < N; i++) {
                if (!dp[i][j]) {
                    tmp++;
                }
            }
            ans = Math.min(ans, tmp);
        }
        return ans;
    }
}
